package prefixTree;

import java.util.List;

/**
 *  题目 ：单词替换
 *  题目详述 ：
 *  在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。
 *  例如，词根an，跟随着单词other(其他)，可以形成新的单词another(另一个)。
 *
 * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
 * 你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
 * 你需要输出替换之后的句子。
 *
 */
public class ReplaceWords {
    /**
     * 核心思想 ：
     * （1）由于存在由许多词根所组成的词典dictionary；首先构建前缀树，将组成词根的字符逐个加入到前缀树中（prefixTree）
     * （2）由于sentence使用空格来对于句子进行单词分割，使用空格分隔符，将句子中的单词获取，同时存放到字符串数组中；
     * （3）遍历字符串数组，同时去词典dictionary中去获取当前遍历字符串的前缀是否出现，
     *      即根据前缀树节点的isWord树形，去判断是否从根节点到当前遍历的节点所组成的字符串，是已经存储入词典的单词
     * @param dictionary
     * @param sentence
     * @return
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = buildTrieNode(dictionary);
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length ; i++) {
            String prefix = findPrefix(root, words[i]);
            if(prefix != ""){
                words[i] = prefix;
            }
        }
        return String.join(" ",words);
    }

    // (1)将词典中的所有单词，存储入前缀树中；
    // 注意 ：此方法的返回值，需要是TrieNode节点（前缀树的根节点root）；
    // 即，有且仅有返回所构建的前缀树的根节点，其他方法才能够通过根节点去访问所构建的前缀树；
    public TrieNode buildTrieNode(List<String> dictionary){
        // 初始化根节点
        TrieNode root = new TrieNode();
        for (String s : dictionary) {
            // 每次遍历词典中的单词，都需要从根节点开始，将此单词中所包含的字符存储到前缀树中
            TrieNode node = root;
            // 遍历单词中的所有字符；
            // 考虑两种情况 ：
            // （1）当前字符在前缀树中已经存在，那么只需要将node节点后移即可
            // （2）当前字符在前缀树中不存在，即需要新建前缀树节点来存储当前字符，同时将node节点后移到新建前缀树节点；
            for (char c : s.toCharArray()) {
                if(node.children[c - 'a'] == null){
                    // 新建前缀树节点
                    node.children[c - 'a'] = new TrieNode();
                }
                // node节点后移
                node = node.children[c - 'a'];
            }
            // 即，遍历单词结束，当前node节点所指向的是遍历完单词的最后一个字符；
            // 通过将此单词的最后一个字符isWord，改为true，从而来指明根节点到当前节点所构成的字符串为一个单词
            node.isWord = true;
        }
        return root;
    }

    // (2)判断传入单词，是否存在前缀（prefix）
    // 所需要传入的参数：
    // （1）前缀树的根节点（用于去遍历前缀树，获取当前单词是否在前缀树中存在前缀）；
    // （2）所要判断的单词；
    public String findPrefix(TrieNode root,String word){
        TrieNode node = root;
        // 新创建字符串（StringBuffer），用于拼接字符串；
        // 若是此单词在前缀树中并不存在对应的单词的话，那么就返回空字符串，否则的话返回拼接字符串
        StringBuffer newString = new StringBuffer();
        for (char c : word.toCharArray()) {
            // 若是当前单词正在遍历的字符不存在于前缀树中话，直接跳出循环;
            // 或者是 当前单词正在遍历的字符isWord属性为true，即已经获取到前缀（prefix），跳出循环即可；
            if(node.children[c - 'a'] == null || node.isWord){
                break;
            }
            // 将当前正在遍历的字符添加到新建的字符串后面，同时node节点后移；
            newString.append(c);
            node = node.children[c - 'a'];
        }
        // 若是当前单词正在遍历的字符不存在于前缀树中的话/遍历完整个字符串同时字符串的最后一个字符的isWord不为true，即返回空字符串
        // 若是由于当前单词由于正在遍历的字符isWord属性为true 退出循环的，那么就返回新建的字符串
        return node.isWord == true ? newString.toString() : "";
    }

    /**
     * 分析 ：
     * （1）构建前缀树的时候，必须先初始化根节点，通过根节点去构建前缀树，同时若是要使得别人能够使用所构建的二叉树，需要使得返回值为前缀树的root节点；
     * （2）前缀树的结构为 子数组（用来保存所有可能的字符） + isWord（用来判断此节点是否为词典中某个单词的最后一个字符）；
     * （3）单词是否存在前缀的判断 ：即，满足（1）遍历的字符都存在于前缀树中，（2）同时，最后一个字符所对应的前缀树节点属性isWord为true，才能够确定当前单词有前缀（prefix）
     * （4）时间复杂度：
     * 1.构建和初始化前缀树：O（m*n）（m，为词根数量；同时，n为单词平均长度）；
     * 2.寻找前缀 ：O（n）（n，为单词平均长度）
     * 总的时间复杂度 ：O(m*n)
     */
}
